\(b\)-coloring of tight graphs

DOI10.1016/j.dam.2011.10.017zbMath1292.05111MaRDI QIDQ1759847

Frédéric Havet, Leonardo Sampaio, Cláudia Linhares Sales

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.017

zbMATH Keywords

graph coloring; tight graphs; \(b\)-coloring; precoloring extension

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

05C07: Vertex degrees

Related Items

Unnamed Item, A complexity dichotomy for critical values of the b-chromatic number of graphs, A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs, \(b\)-continuity and the lexicographic product of graphs, On the parameterized complexity of b-\textsc{chromatic number}, Graphs with large girth are \(b\)-continuous, \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs, The \(b\)-chromatic number and related topics -- a survey, The \(b\)-continuity of graphs with large girth, On the \(b\)-continuity of the lexicographic product of graphs, Edge-\(b\)-coloring trees, Graphs with small fall-spectrum, On the Grundy and \(b\)-chromatic numbers of a graph, Graphs with girth at least 8 are b-continuous, Well-partitioned chordal graphs, \(b\)-continuity and partial Grundy coloring of graphs with large girth, A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic, A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs, Graphs of girth at least 7 have high \(b\)-chromatic number, The \(b\)-chromatic index of graphs, The lexicographic product of some chordal graphs and of cographs preserves \(b\)-continuity, An integer programming approach to b-coloring, The b-Chromatic Number of Some Standard Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• An introduction to timetabling
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• The b-chromatic number of a graph
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• Bounds for the b-chromatic number of some families of graphs
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A New Class of Brittle Graphs
• The NP-Completeness of Edge-Coloring
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Efficient algorithms for graphs with few \(P_4\)'s