Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs
A hypergraph is called k-chromatic if its vertex set can be partitioned into at most k pairwise disjoint subsets when each subset has no more than two common vertices with every edge of the hypergraph. The multiplicity of a pair of vertices in a hypergraph is the number of hypergraph edges containin...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
2018-12-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/443 |
| _version_ | 1797877342107860992 |
|---|---|
| author | T. V. Lubasheva |
| author_facet | T. V. Lubasheva |
| author_sort | T. V. Lubasheva |
| collection | DOAJ |
| description | A hypergraph is called k-chromatic if its vertex set can be partitioned into at most k pairwise disjoint subsets when each subset has no more than two common vertices with every edge of the hypergraph. The multiplicity of a pair of vertices in a hypergraph is the number of hypergraph edges containing the pair of vertices. The multiplicity of a hypergraph is the maximum multiplicity of the pairs of vertices. Let Lm(k) denote the class of edge intersection graphs of k-chromatic hypergraphs with multiplicity at most m. It is known that the problem of recognizing graphs from L1(k) is polynomially solvable if k = 2 and is NP-complete if k = 3. The complexity of the recognition of graphs from Lm(k) for fixed k ≥ 2 and m ≥ 2 is currently unknown.A split graph is a graph whose vertices can be partitioned into a clique and an independent set. It is known that for any k ≥ 2 the graphs from L1(k) can be characterized by a finite list of forbidden induced subgraphs in the class of split graphs. It was earlier proved that there exists a finite characterization in terms of forbidden induced subgraphs for the graphs from L2(3) in the class of split graphs.It is proved in the article that a finite characterization in terms of forbidden induced subgraphs for the graphs from Lm(3) (for fixed m ≥ 2) exists in the class of split graphs. In particular, it follows that the problem of recognizing graphs from Lm(3), m ≥ 2 is polynomially solvable in the class of split graphs. |
| first_indexed | 2024-04-10T02:15:38Z |
| format | Article |
| id | doaj.art-e1f0227581bc454cacd9f2aeb31b198a |
| institution | Directory Open Access Journal |
| issn | 1816-0301 |
| language | Russian |
| last_indexed | 2024-04-10T02:15:38Z |
| publishDate | 2018-12-01 |
| publisher | The United Institute of Informatics Problems of the National Academy of Sciences of Belarus |
| record_format | Article |
| series | Informatika |
| spelling | doaj.art-e1f0227581bc454cacd9f2aeb31b198a2023-03-13T08:32:20ZrusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusInformatika1816-03012018-12-01154102108443Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphsT. V. Lubasheva0Belarus State Economic UniversityA hypergraph is called k-chromatic if its vertex set can be partitioned into at most k pairwise disjoint subsets when each subset has no more than two common vertices with every edge of the hypergraph. The multiplicity of a pair of vertices in a hypergraph is the number of hypergraph edges containing the pair of vertices. The multiplicity of a hypergraph is the maximum multiplicity of the pairs of vertices. Let Lm(k) denote the class of edge intersection graphs of k-chromatic hypergraphs with multiplicity at most m. It is known that the problem of recognizing graphs from L1(k) is polynomially solvable if k = 2 and is NP-complete if k = 3. The complexity of the recognition of graphs from Lm(k) for fixed k ≥ 2 and m ≥ 2 is currently unknown.A split graph is a graph whose vertices can be partitioned into a clique and an independent set. It is known that for any k ≥ 2 the graphs from L1(k) can be characterized by a finite list of forbidden induced subgraphs in the class of split graphs. It was earlier proved that there exists a finite characterization in terms of forbidden induced subgraphs for the graphs from L2(3) in the class of split graphs.It is proved in the article that a finite characterization in terms of forbidden induced subgraphs for the graphs from Lm(3) (for fixed m ≥ 2) exists in the class of split graphs. In particular, it follows that the problem of recognizing graphs from Lm(3), m ≥ 2 is polynomially solvable in the class of split graphs.https://inf.grid.by/jour/article/view/443edge intersection graph of hypergraphforbidden induced subgraphcharacterizationsplit graphk-chromatic hypergraphcoloring |
| spellingShingle | T. V. Lubasheva Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs Informatika edge intersection graph of hypergraph forbidden induced subgraph characterization split graph k-chromatic hypergraph coloring |
| title | Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| title_full | Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| title_fullStr | Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| title_full_unstemmed | Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| title_short | Characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| title_sort | characterization and recognition of edge intersection graphs of trichromatic hypergraphs with finite multiplicity in the class of split graphs |
| topic | edge intersection graph of hypergraph forbidden induced subgraph characterization split graph k-chromatic hypergraph coloring |
| url | https://inf.grid.by/jour/article/view/443 |
| work_keys_str_mv | AT tvlubasheva characterizationandrecognitionofedgeintersectiongraphsoftrichromatichypergraphswithfinitemultiplicityintheclassofsplitgraphs |