- On graphs with maximum difference between game chromatic number and chromatic number
2023/09/04 by Lawrence Hollom, Hollom, Lawrence · 1 citation
Computer Science · Mathematics · #05C57 #Advanced Graph Theory Research #Brooks' theorem #Chromatic scale #Combinatorics #Combinatorics (math.CO) #Complete coloring #Conjecture #Discrete mathematics #FOS: Mathematics #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Vertex (graph theory) #Windmill graph
- No distributed quantum advantage for approximate graph coloring
2023/07/18 by Xavier Coiteux-Roy, Coiteux-Roy, Xavier, Francesco d’Amore +20 · 2 voices · 6 citations
Computer Science · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Distributed algorithm #Distributed computing #Distributed systems and fault tolerance #Edge coloring #Graph #Graph coloring #Graph power #Line graph #Matching (statistics) #Mathematics #Omega #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum mechanics #Upper and lower bounds
- On the Signed Complete Graphs with Maximum Index
2021/02/05 by Navid Kafai, Kafai, N., F. Heydari +5 · 1 citation
Computer Science · Mathematics · #Adjacency matrix #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #Eigenvalues and eigenvectors #FOS: Mathematics #Finite Group Theory Research #Graph #Graph Labeling and Dimension Problems #Graph power #Graph theory and applications #Line graph #Mathematics #Physics #Signed graph #Two-graph #Vertex (graph theory)
- Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring
2020/07/21 by Or Zamir · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Brooks' theorem #Chordal graph #Chromatic scale #Combinatorics #Complete coloring #Computer science #Degree (music) #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Line graph #List coloring #Mathematics #Physics #Theoretical computer science #graph theory and CDMA systems
- Strong chromatic index of K 1 , t -free graphs
2020/03/21 by Michał Dębski, Konstanty Junosza-Szaniawski, Małgorzata Śleszyńska-Nowak · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Conjecture #Discrete mathematics #Edge coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Limits and Structures in Graph Theory #Line graph #Mathematical analysis #Mathematics #Upper and lower bounds
- Sharp upper bounds of the spectral radius of a graph
2019/06/06 by Ji-Ming Guo, Ji‐Ming Guo, Yidong Wang +2 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Adjacency matrix #Bound graph #Combinatorics #Complex Network Analysis Techniques #Connectivity #Discrete mathematics #Eigenvalues and eigenvectors #Graph #Graph Labeling and Dimension Problems #Graph energy #Graph power #Graph theory and applications #Line graph #Mathematical analysis #Mathematics #Physics #Simple graph #Spectral radius #Upper and lower bounds #Vertex (graph theory)
- Excluded minors in cubic graphs
2019/02/19 by Neil Robertson, Paul Seymour, Robin Thomas · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics #Computer science #Cubic graph #Discrete mathematics #Embedding #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Partition (number theory) #Petersen graph #Planar graph #Polyhedral graph #Vertex (graph theory) #Voltage graph
- A survey on the missing Moore graph
2019/01/16 by C. Dalfó · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Distance #Distance-regular graph #Finite Group Theory Research #Frequency partition of a graph #Graph #Graph power #Line graph #Mathematics #Neighbourhood (mathematics) #Path graph #Strongly regular graph #Symmetric graph #Vertex (graph theory) #Vertex-transitive graph #Voltage graph #Wheel graph #graph theory and CDMA systems
- The distinguishing chromatic number of bipartite graphs of girth at least six
2017/09/28 by Saeid Alikhani, Saeid Alikhani, Samaneh Soltani +2 · 1 citation
Computer Science · Mathematics · #05C15 #05C25 #Bipartite graph #Chromatic scale #Combinatorics #Combinatorics (math.CO) #Conjecture #Discrete mathematics #Edge coloring #Edge-transitive graph #FOS: Mathematics #Foster graph #Girth (graph theory) #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Triangle-free graph #Vertex (graph theory) #math.CO #msc:05C15 #msc:05C25
- Algorithmic Aspects of Regular Graph Covers
2016/09/10 by Jiří Fiala, Jiřı́ Fiala, Fiala, Jiří +7 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Bijection #Combinatorics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Graph #Graph homomorphism #Graph isomorphism #Graph power #Group Theory (math.GR) #Homomorphism #Isomorphism (crystallography) #Limits and Structures in Graph Theory #Line graph #Mathematics #Planar graph #Time complexity #Ubiquitin and proteasome pathways #cs.DM #math.CO #math.GR
- 1-Planar Graphs have Constant Book Thickness
2015/01/01 by Michael A. Bekos, Till Bruckdorfer, Michael Kaufmann +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Book embedding #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Discrete mathematics #Embedding #Graph #Graph power #Line graph #Mathematical analysis #Mathematics #Optimization and Search Problems #Path graph #Planar graph #Planar straight-line graph #Upper and lower bounds
- On the Algorithmic Lovász Local Lemma and Acyclic Edge Coloring
2014/12/22 by Ioannis Giotis, Lefteris M. Kirousis, Kostas I. Psaromiligkos +1 · 1 citation
Mathematics · Computer Science · Biochemistry, Genetics and Molecular Biology · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Genome Rearrangement Algorithms #Upper and lower bounds #Combinatorics #Edge coloring #Lemma (botany) #Mathematics #Discrete mathematics #Bounded function #Directed acyclic graph #Graph #Graph power #Line graph
- Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
2014/02/28 by Daniel J. Harvey, David R. Wood · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Combinatorics #Treewidth #Mathematics #Discrete mathematics #Disjoint sets #Graph minor #Graph #Vertex (graph theory) #Cubic graph #Outerplanar graph #Partial k-tree #Graph power #1-planar graph #Line graph #Pathwidth #Voltage graph
- The maximum ratio clique problem
2013/11/06 by Samyukta Sethuraman, Sergiy Butenko · 1 citation
Computer Science · Decision Sciences · Mathematics · #Chordal graph #Clique #Clique graph #Clique problem #Combinatorics #Completeness (order theory) #Complexity and Algorithms in Graphs #Graph #Graph power #Line graph #Mathematical optimization #Mathematics #Optimization and Search Problems #Risk and Portfolio Optimization
- Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
2011/12/09 by Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Biconnected graph #Book embedding #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Embedding #Graph #Graph power #Intersection (aeronautics) #Line graph #Mathematics #Outerplanar graph #Pathwidth #Planar graph #Planar straight-line graph #Time complexity #Vertex (graph theory)
- Graphs with maximum degree 5 are acyclically 7-colorable
2011/03/24 by Alexandr Kostochka, Christopher Stocker · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Degree (music) #Complete coloring #List coloring #Edge coloring #Greedy coloring #Graph #Fractional coloring #Discrete mathematics #Graph coloring #Property (philosophy) #Graph power #Line graph
- How to Draw a Tait-Colorable Graph
2011/01/01 by David A. Richter · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Edge coloring #Enhanced Data Rates for GSM Evolution #Geometry #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Line (geometry) #Line graph #Mathematics
- Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
2010/07/23 by Martin Kochol · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Conjecture #Cubic graph #Discrete mathematics #Disjoint sets #Edge coloring #Embedding #Geometry #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Polyhedral graph #Simple (philosophy) #Surface (topology) #Voltage graph
- An output sensitive algorithm for computing a maximum independent set of a circle graph
2010/05/25 by Nicholas Nash, David Gregg · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Circle graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Graph #Graph algorithms #Graph power #Line graph #Mathematics #Optimization and Search Problems #Vertex (graph theory)
- Acyclic Vertex Coloring of Graphs of Maximum Degree Six
2009/12/01 by Satish Varagani, V. Ch. Venkaiah, V.Ch. Venkaiah +2 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Brooks' theorem #Chordal graph #Combinatorics #Complete coloring #Degree (music) #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Physics #Vertex (graph theory)
- Weak graph colorings
2009/08/11 by Fabian Kühn · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research #Combinatorics #Graph #Edge coloring #Mathematics #Fractional coloring #Graph coloring #Greedy coloring #Complete coloring #Degree (music) #Chromatic scale #Discrete mathematics #List coloring #Binary logarithm #Graph power #Line graph #Physics
- The road coloring problem
2009/07/01 by A. N. Trahtman · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Cellular Automata and Applications #Combinatorics #Complete coloring #Computer science #DNA and Biological Computing #Deterministic automaton #Deterministic finite automaton #Discrete mathematics #Finite-state machine #Graph #Graph power #Greedy coloring #Line graph #List coloring #Mathematics #Nondeterministic finite automaton #Strongly connected component #Synchronizing #Theoretical computer science #Topology (electrical circuits) #Two-way deterministic finite automaton #semigroups and automata theory
- Improved edge-coloring with three colors
2009/05/10 by Łukasz Kowalik · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Line graph #Mathematics #Time complexity #Vertex (graph theory)
- On list critical graphs
2008/06/26 by Michael Stiebitz, Źsolt Tuza, Zsolt Tuza +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Critical graph #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph factorization #Graph power #Induced subgraph #Limits and Structures in Graph Theory #Line graph #Mathematics #Vertex (graph theory)
- Acyclic coloring of graphs of maximum degree five: Nine colors are enough
2007/09/04 by Guillaume Fertin, André Raspaud · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Brooks' theorem #Chromatic scale #Combinatorics #Complete coloring #Degree (music) #Directed acyclic graph #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics
- Improved bounds on acyclic edge colouring
2007/03/19 by Rahul Muthu, N. Narayanan, C.R. Subramanian +1 · 2 citations
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Computer science #Directed acyclic graph #Discrete mathematics #Edge coloring #Enhanced Data Rates for GSM Evolution #Girth (graph theory) #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Nuclear Receptors and Signaling #Upper and lower bounds
- There are exactly five biplanes with k = 11
2007/02/22 by Petteri Kaski, Patric R. J. Östergård · 1 citation
Engineering · Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #graph theory and CDMA systems #Coding theory and cryptography #Genomic variations and chromosomal abnormalities #Mathematics #Combinatorics #Graph #Residual #Biplane #Strongly regular graph #Discrete mathematics #Algorithm #Graph power #Line graph
- Strong edge-coloring of graphs with maximum degree 4 using 22 colors
2006/08/25 by Daniel W. Cranston · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Bounded function #Brooks' theorem #Chordal graph #Combinatorics #Complete coloring #Computer science #Conjecture #Degree (music) #Discrete mathematics #Edge coloring #Enhanced Data Rates for GSM Evolution #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Simple (philosophy) #Simple graph #Upper and lower bounds
- Results on the Grundy chromatic number of graphs
2006/08/08 by Manouchehr Zaker · 1 citation
Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Brooks' theorem #Chordal graph #Colored #Combinatorics #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Vertex (graph theory) #graph theory and CDMA systems
- An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments
2006/07/06 by Etsuji Tomita, Toshikatsu Kameda · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Benchmark (surveying) #Branch and bound #Clique #Clique graph #Clique problem #Combinatorics #Complexity and Algorithms in Graphs #Computation #DNA and Biological Computing #Discrete mathematics #Graph #Graph power #Line graph #Mathematics #Pathwidth #Random graph #Upper and lower bounds
more