scientific article; zbMATH DE number 3889564
From MaRDI portal
Publication:3222874
[For the entire collection see Zbl 0546.00006.] A parity graph is a graph in which for every pair of vertices (x,y), the lengths of the minimal x,y-paths all have the same parity. The authors characterize these graphs, and observe that they are all perfect graphs. They then discuss polynomial algorithms for recognizing parity graphs, and for determining the maximum stable set, minimum colouring, minimum covering by cliques and maximum clique of a parity graph.
Recommendations
- Convex parity graphs
- Parity dimension for graphs
- Graph decomposition and parity
- Parity equivalence in eulerian graphs
- Parity and disparity subgraphs
- Highly parity linked graphs
- Parallel algorithms for parity graphs
- On parity combination cordial graphs
- Parity combination cordial labeling of graphs
- Metric characterization of parity graphs
Cited in
(47)- Parity and disparity subgraphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Murky graphs
- Locally perfect graphs
- A fast algorithm for coloring Meyniel graphs
- Parity graphs are kernel-M-solvable
- Connected sequential colourings
- Dominating sets in perfect graphs
- Metric characterization of parity graphs
- On slim graphs, even pairs, and star-cutsets
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- On perfectness of sums of graphs
- On the extension of bipartite to parity graphs
- Graph classes between parity and distance-hereditary graphs
- On \(m\)-centers in \(P_ t\)-free graphs
- \(k\)-NLC graphs and polynomial algorithms
- Path parity and perfection
- On the optimal transversals of the odd cycles
- Parity dimension for graphs
- Twin subgraphs and core-semiperiphery-periphery structures
- Minimax relations for the partial q-colorings of a graph
- Unavoidable doubly connected large graphs
- The clique operator on cographs and serial graphs
- The parity path problem on some subclasses of perfect graphs
- The complexity of the parity argument with potential
- How to compute digraph width measures on directed co-graphs
- Classes of perfect graphs
- Two-colourings that decompose perfect graphs
- Counting all parity realizable trees
- Parallel algorithms for parity graphs
- A new characterization for parity graphs and a coloring problem with costs
- Graph classes between parity and distance-hereditary graphs
- scientific article; zbMATH DE number 1308945 (Why is no real title available?)
- scientific article; zbMATH DE number 653251 (Why is no real title available?)
- Practical and efficient split decomposition via graph-labelled trees
- Parity Dimension for Graphs - A Linear Algebraic Approach
- scientific article; zbMATH DE number 822749 (Why is no real title available?)
- scientific article; zbMATH DE number 871170 (Why is no real title available?)
- Reconstruction of 2-connected parity graphs
- Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
- Skeletal graphs - a new class of perfect graphs
- The axiomatic characterization of the interval function of distance hereditary graphs
- Weighted connected domination and Steiner trees in distance-hereditary graphs (extended abstract)
- Perfectly contractile graphs
- Parity versions of 2-connectedness
- Parallel recognition of complement reducible graphs and cotree construction
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3222874)