Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Colouring square-free graphs without long induced paths - MaRDI portal

Colouring square-free graphs without long induced paths (Q2323345)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Colouring square-free graphs without long induced paths	scientific article

Statements

scholarly article

0 references

Colouring square-free graphs without long induced paths (English)

0 references

0 references

0 references

Daniël Paulusma

0 references

Journal of Computer and System Sciences

0 references

publication date

30 August 2019

0 references

full work available at URL

https://arxiv.org/abs/1805.08270

0 references

https://drops.dagstuhl.de/opus/volltexte/2018/8492/

0 references

zbMATH Keywords

graph colouring

0 references

forbidden induced subgraphs

0 references

clique-width

0 references

atoms

0 references

MaRDI profile type

MaRDI publication profile

0 references

On rank-width of even-hole-free graphs

0 references

Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths

0 references

Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide

0 references

Clique cutsets beyond chordal graphs

0 references

Three-coloring and list three-coloring of graphs without induced paths on seven vertices

0 references

On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem

0 references

0 references

Graph Classes: A Survey

0 references

Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time

0 references

Solving the clique cover problem on (bull, \(C_4\))-free graphs

0 references

Triangle-free graphs with no six-vertex induced path

0 references

3-Colorable Subclasses of $P_8$-Free Graphs

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Upper bounds to the clique width of graphs

0 references

Improved Bounds for the Flat Wall Theorem

0 references

Colouring diamond-free graphs

0 references

Colouring of graphs with Ramsey-type forbidden subgraphs

0 references

On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs

0 references

On rigid circuit graphs

0 references

Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

0 references

0 references

Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs

0 references

Colouring square-free graphs without long induced paths.

0 references

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

0 references

List coloring in the absence of two subgraphs

0 references

Coloring graphs without short cycles and long induced paths

0 references

Algorithmic graph theory and perfect graphs

0 references

Coloring the hypergraph of maximal cliques of a graph with no long path

0 references

0 references

Complexity of coloring graphs without paths and cycles

0 references

Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time

0 references

Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes

0 references

The NP-Completeness of Edge-Coloring

0 references

Improved complexity results on \(k\)-coloring \(P_t\)-free graphs

0 references

Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs

0 references

0 references

Recent developments on graphs of bounded clique-width

0 references

Polynomial cases for the vertex coloring problem

0 references

Square-Free Graphs with No Six-Vertex Induced Path

0 references

Edge dominating set and colorings on graphs with fixed clique-width

0 references

0 references

NP completeness of finding the chromatic index of regular graphs

0 references

0 references

Vertex coloring of graphs with few obstructions

0 references

0 references

ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P<sub>4</sub>'S

0 references

The coloring problem for classes with two small obstructions

0 references

Two cases of polynomial-time solvability for the coloring problem

0 references

Two complexity results for the vertex coloring problem

0 references

Graph colouring and the probabilistic method

0 references

Approximating clique-width and branch-width

0 references

MSOL partitioning problems on graphs of bounded treewidth and clique-width

0 references

Some new hereditary classes where graph coloring remains NP-hard

0 references

On a property of the class of n-colorable graphs

0 references

Decomposition by clique separators

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/j.jcss.2019.06.002

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2323345

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2323345&oldid=36520982"