- 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
- Improved square coloring of planar graphs
2022/12/13 by Nicolas Bousquet, Nicolás Bousquet, Quentin Deschamps +3 · 4 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Brooks' theorem #Chordal graph #Combinatorics #Complete coloring #Computer science #Conjecture #Degree (music) #Discrete mathematics #Edge coloring #Fractional coloring #Geometry #Graph #Graph coloring #Graph power #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Optimization and Search Problems #Planar #Planar graph #Square (algebra) #Total coloring
- 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
- 3-dynamic coloring of planar triangulations
2018/08/10 by Yoshihiro Asayama, Yuki Kawasaki, Seog‐Jin Kim +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chromatic scale #Combinatorics #Complete coloring #Computer science #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 #Planar #Planar graph #Vertex (graph theory)
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
2016/11/08 by Leonid Barenboim · 6 citations
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Complete coloring #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Line graph #List coloring #Mathematics #Optimization and Search Problems #Sublinear function #Upper and lower bounds #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
- 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 · 2 citations
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
- 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
- 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
- On the equality of the partial Grundy and upper ochromatic numbers of graphs
2003/09/16 by Paul Erdős, Paul Erdös, Stephen T. Hedetniemi +4 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complete coloring #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics #Partition (number theory) #Vertex (graph theory)
- On the coloration of perfect graphs
2003/01/01 by Frédéric Maffray, F. Maffray · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Brooks' theorem #Chordal graph #Chromatic scale #Combinatorics #Complete coloring #Discrete mathematics #Edge coloring #Graph #Graph Labeling and Dimension Problems #Graph power #Limits and Structures in Graph Theory #Line graph #Mathematics #Partition (number theory)
- The complexity of path coloring and call scheduling
2001/03/01 by Thomas Erlebach, Klaus Jansen · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Optical Network Technologies #Approximation algorithm #Combinatorics #Communication complexity #Complete coloring #Computer science #Discrete mathematics #Fractional coloring #Graph #Graph coloring #Interconnection Networks and Systems #Mathematical optimization #Mathematics #Scheduling (production processes) #Time complexity
- On Coloring Unit Disk Graphs
1998/03/01 by Albert Gräf, A. Gräf, M. Stumpf +2 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Chordal graph #Combinatorics #Complete coloring #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Edge coloring #Graph #Graph coloring #Greedy coloring #Indifference graph #Intersection (aeronautics) #Line graph #Matching (statistics) #Mathematics #Theory of computation #Unit disk #Unit disk graph #graph theory and CDMA systems
- On the complexity of H-coloring
1990/02/01 by Pavol Hell, Jaroslav Nešetřil · 9 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complete coloring #Discrete mathematics #Edge coloring #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph homomorphism #Graph power #Greedy coloring #Limits and Structures in Graph Theory #Line graph #List coloring #Mathematics
- On‐line and first fit colorings of graphs
1988/06/01 by András Gyárfás, Jenő Lehel · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Optimization and Search Problems #Complexity and Algorithms in Graphs #Combinatorics #Greedy coloring #Mathematics #Complete coloring #Chordal graph #Graph coloring #Interval graph #Fractional coloring #Edge coloring #List coloring #Discrete mathematics #Split graph #Bounded function #Brooks' theorem #Graph #Indifference graph #Line graph #1-planar graph #Graph power
- Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
1986/01/01 by Andrzej Proskurowski, Maciej M. Sysło · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Edge coloring #Outerplanar graph #Discrete mathematics #Vertex (graph theory) #Brooks' theorem #Complete coloring #Chromatic scale #Pathwidth #Graph #1-planar graph #Chordal graph #Graph power #Line graph
- On Edge Coloring Bipartite Graphs
1982/08/01 by Richard Cole, John E. Hopcroft · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Computational Geometry and Mesh Generation #Bipartite graph #Combinatorics #Edge coloring #Mathematics #Graph coloring #Complete bipartite graph #Complete coloring #List coloring #Enhanced Data Rates for GSM Evolution #Discrete mathematics #Fractional coloring #Graph #Graph power #Computer science #Line graph
- The Complexity of Coloring Circular Arcs and Chords
1980/06/01 by M. R. Garey, David S. Johnson, Gary L. Miller +1 · 15 citations
Computer Science · Mathematics · Engineering · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems #Mathematics #Combinatorics #Graph coloring #Arc (geometry) #Fractional coloring #Greedy coloring #List coloring #Complete coloring #Discrete mathematics #Graph #Graph power #Line graph #Geometry
- Some perfect coloring properties of graphs
1979/08/01 by C. Christen, Claude A Christen, Stanley M. Selkow +1 · 5 citations
Computer Science · Mathematics · #1-planar graph #Achromatic lens #Advanced Graph Theory Research #Brooks' theorem #Chordal graph #Chromatic scale #Clique number #Cograph #Combinatorics #Complete coloring #Discrete mathematics #Fractional coloring #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Line graph #Mathematics #Physics #Split graph
- Acyclic colorings of planar graphs
1973/12/01 by Branko Grünbaum · 11 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Arboricity #Combinatorics #Complete coloring #Computational Geometry and Mesh Generation #Conjecture #Discrete mathematics #Edge coloring #Graph #Graph coloring #Graph power #Greedy coloring #Line graph #List coloring #Mathematics #Planar graph #graph theory and CDMA systems