Point partition numbers: perfect graphs

DOI10.1007/S00373-021-02410-WzbMATH Open1484.05080arXiv2003.04657OpenAlexW4210397733MaRDI QIDQ2115144FDOQ2115144

Authors: Justus von Postel, Thomas Schweser, Michael Stiebitz 

Publication date: 15 March 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer $tgeq1$, denote by $mathcal{MG}_t$ the class of graphs whose maximum multiplicity is at most $t$. A graph $G$ is called strictly $t$-degenerate if every non-empty subgraph $H$ of $G$ contains a vertex $v$ whose degree in $H$ is at most $t-1$. The point partition number $ch{i}_t(G)$ of $G$ is smallest number of colors needed to color the vertices of $G$ so that each vertex receives a color and vertices with the same color induce a strictly $t$-degenerate subgraph of $G$. So $ch{i}_1$ is the chromatic number, and $ch{i}_2$ is known as the point aboricity. The point partition number $ch{i}_t$ with $tgeq1$ was introduced by Lick and White. If $H$ is a simple graph, then $tH$ denotes the graph obtained from $H$ by replacing each edge of $H$ by $t$ parallel edges. Then $omeg{a}_t(G)$ is the largest integer $n$ such that $G$ contains a $t{K}_n$ as a subgraph. Let $G$ be a graph belonging to $mathcal{MG}_t$. Then $omeg{a}_t(G)leqch{i}_t(G)$ and we say that $G$ is $ch{i}_t$-perfect if every induced subgraph $H$ of $G$ satisfies $omeg{a}_t(H)=ch{i}_t(H)$. Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas, we give a characterization of $ch{i}_t$-perfect graphs of $mathcal{MG}_t$ by a set of forbidden induced subgraphs. We also discuss some complexity problems for the class of $ch{i}_t$-critical graphs.

Full work available at URL: https://arxiv.org/abs/2003.04657

Recommendations

• Point partition numbers: decomposable and indecomposable critical graphs
• scientific article
• On generalized perfect graphs: Bounded degree and bounded edge perfection
• On claw-free \(t\)-perfect graphs
• Perfect graphs

zbMATH Keywords

degeneracyperfect graphspoint partition number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• Normal hypergraphs and the perfect graph conjecture
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization.
• A characterization of perfect graphs
• k-Degenerate Graphs
• The strong perfect graph theorem
• Recognizing Berge graphs
• Finding an induced subdivision of a digraph
• Perfect digraphs
• Optimal Vertex Partitions
• Minimal imperfect graphs: A simple approach
• On Partitioning Planar Graphs
• On characterizing game-perfect graphs by forbidden induced subgraphs
• Hajós and Ore constructions for digraphs

Cited In (2)

• Title not available (Why is that?)
• Point partition numbers: decomposable and indecomposable critical graphs

This page was built for publication: Point partition numbers: perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115144)