\(b\)-coloring of tight graphs

DOI10.1016/j.dam.2011.10.017zbMath1292.05111OpenAlexW2179374792MaRDI 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 coloringtight graphs\(b\)-coloringprecoloring extension

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (23)

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

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

This page was built for publication: \(b\)-coloring of tight graphs